package com.gitee.ed.arithmetic.leetcode.answer.answer_1_100.answer_1_10;

import com.gitee.ed.arithmetic.leetcode.solution.solution_1_100.solution_1_10.Solution2;
import com.gitee.ed.arithmetic.leetcode.struct.ListNode;

/**
 * @author hongda.li
 */
public class Answer2 implements Solution2 {

    @Override
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode();
        ListNode temp = head;

        // 是否需要进位
        boolean carry = false;

        // 两个链表长度可能不一样
        // 遍历链表至尾节点
        while (l1 != null || l2 != null) {
            // 链表为空则补0
            int i1 = l1 == null ? 0 : l1.val;
            int i2 = l2 == null ? 0 : l2.val;

            // 求和 = 链表相同位数相加 + 进位
            int sum = i1 + i2 + (carry ? 1 : 0);

            // 对 10 取余数可得到个位数
            temp.val = sum % 10;

            // 如果取余数后有变化，则需进一位
            carry = temp.val != sum;

            // 遍历下一个节点
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }

            if (l1 != null || l2 != null) {
                temp.next = new ListNode();
                temp = temp.next;
            }
        }

        // 如需进位则补1
        if (carry) {
            temp.next = new ListNode(1);
        }

        return head;
    }
}
